package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//17. 电话号码的字母组合
//
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
//
//给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//
//
//示例:
//
//输入："23"
//输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
//说明:
//尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

public class Solution017 {

	public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
        	return res;
        }
        
        String[] map = new String[10];
        map[2] = "abc";
        map[3] = "def";
        map[4] = "ghi";
        map[5] = "jkl";
        map[6] = "mno";
        map[7] = "pqrs";
        map[8] = "tuv";
        map[9] = "wxyz";
        
        dfs(digits.toCharArray(), map, 0, res, "");
        
        return res;
    }
	
	
	private void dfs(char[] c, String[] map, int start, List<String> res, String path) {
		
		if (path.length() == c.length) {
			res.add(path);
			return;
		}
		
		for (int i=start; i<c.length; i++) {
			
			String val = map[c[i] - '0'];
			
			for (char v : val.toCharArray()) {
				dfs(c, map, i+1, res, path+v);
			}
		}
		
		
	}
	
	
}
